package irg.bhavani.binarytree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Node{

	int val;
	Node right;
	Node left;

}
public class AddingElem {

	Node root ; 


	public void addElement(int element){

		Node current = root;
		Node n  = new Node();
		n.val = element;
		boolean added = false;
		if(root == null){
			root = n;
			//System.out.println("The element is added at root "+ n.val);
		}
		else{
			while(added == false){

				if(element > current.val){

					if(current.right == null){

						current.right = n;
						added = true;
						//System.out.println("The element is added at right of Current "+ n.val);

					}
					else{

						current = current.right;
					}

				}
				else{

					if(current.left == null){

						current.left = n;
						added = true;
						//	System.out.println("The element is added at right of left "+ n.val);


					}
					else{
						current = current.left;

					}
				}
			}
		}

	}

	public void bearthfirTrav(){
		LinkedList<Node> q = new LinkedList<Node>();
		q.addFirst(root);

		while(q.isEmpty() == false){
			Node current = q.removeLast();
			System.out.println("The element removed from the node is "+current.val);

			if(current.right != null){
				q.addFirst(current.right);

			}

			if(current.left != null){
				q.addFirst(current.left);
			}
		}

	}
	public void depthfirTrav(){
		Stack<Node> st = new Stack<Node>();
		st.push(root);
		while(st.isEmpty() == false){
			Node current = st.pop();
			System.out.println("The element removed from the node is "+current.val);
			if(current.right != null){
				st.push(current.right);

			}

			if(current.left != null){
				st.push(current.left);
			}
		}
	}
	public void findElement(int element){
		Node current = root;
		Node n  = new Node();
		n.val = element;
		boolean found = false;
		if(root == n){
			System.out.println("Element is found " +n.val);		
		}
		else{
			while(found == false){
				if(element > current.val){
					
					if((current.right).val == element){
						System.out.println("Element is found " +n.val);
						found = true;
					}
					else{
						current = current.right;
					}
					if (current.right == null) {
						System.out.println("Element not found");
						found = true;
					}
				}
				else{
					
					if((current.left).val == element){
						System.out.println("Element is found " +n.val);
						found = true;
					}
					else{
						current = current.left;

					}
					if (current.left == null) {
						System.out.println("Element not found");
						found = true;
					}
				}
			}
		}
	}
	public static void main(String[] args) {
		AddingElem  addele = new AddingElem();
		//int[] a ={1,23,34,43,56,2,4,57,54};
		Node n = new Node();
		n.val = 45;
		addele.addElement(45);
		addele.addElement(450);
		addele.addElement(34);
		addele.addElement(1);
		addele.addElement(56);
		//addele.bearthfirTrav();
		//addele.depthfirTrav();
		addele.findElement(450);
	}

}
